import java.util.ArrayList;
import java.util.HashSet;

/**
 * 数组里的重复数字
 */
public class Solution3 {
    /**
     * 所有操作都在输入数组里进行，不需要额外分配内存，因此空间复杂度为O(1)，时间复杂度为O(n)
     * @param numbers
     * @param length
     * @return
     */
    public boolean duplicate1(int[] numbers, int length){
        ArrayList<Integer> duplication = new ArrayList<>();
        for (int i=0; i < length; i++){
            while (numbers[i] != i){
                if (numbers[numbers[i]] == numbers[i]){
                    duplication.add(numbers[i]);
                    break;
                }
                else swap(numbers, i, numbers[i]);
            }
        }
        if (duplication.isEmpty())
            return false;
        else
            for (int element : duplication){
            System.out.println(element);
            }
            return true;
    }

    public void swap(int[] nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }


    /**
     * 用HashSet的元素不重特性，将输入数组的元素装到HashSet里。这样只需要顺序遍历输入数组一次，时间复杂度为O(n).
     * @param nums
     * @param length
     * @return
     */
    public boolean duplicate2(int[] nums, int length){
        HashSet<Integer> duplication = new HashSet<>();
        for (int i=0; i<length; i++){
            if (!duplication.contains(nums[i])){
                duplication.add(nums[i]);
            }
            else {
                System.out.println(nums[i]);
            }
        }
        return duplication.size() != length;
    }

    /**
     * 不改变输入数组，算法思想类似二分查找，空间复杂度为O(1)
     * @param nums
     * @param length
     * @return
     */
    public int duplicate3(int[] nums, int length){
        int start = 0;
        int end = length - 1;
        while (end > start){
            int middle = (end - start) >> 1 + start;
            int count = countRange(nums, length, start, middle);
            if (end == start){
                if (count > 1)
                    return start;
                else
                    break;
            }
            if (count > middle - start + 1){
                end = middle;
            }
            else start = middle + 1;
        }
        return -1;

    }

    public int countRange(int[] nums, int length, int start, int end){
        int count = 0;
        for (int i = start; i < length; i++){
            if (nums[i] >= start && nums[i] <= end){
                count++;
            }
        }
        return count;
    }

//    public static void main(String[] args){
//        Solution3 demo = new Solution3();
//        int[] nums = {2,3,1,0,2,5,3};
//        demo.duplicate1(nums, nums.length);
//    }

}
